The present invention relates generally to methods and systems for determining potential fields, and more specifically relates to computer implemented method and system for determining potential fields.
With the rapid increase in both component density and operating frequency of integrated circuits, the parasitic coupling capacitance associated with interconnects can pose serious design issues. For example, these issues are prevalent in the design of large-area high-resolution amorphous silicon (xe2x80x9ca-Sixe2x80x9d) arrays for applications in X-ray imaging or active-matrix liquid-crystal displays. In these two specific areas, the number of parasitic capacitances increase with increasing component density, while the interconnect capacitance due to the crossover of the gate and data lines introduces electronic noise, thus undermining the quality of the image. Further, the capacitive coupling due to geometric overlapping between the gate and source/drain electrodes in the TFT can give rise to charge feed through thus lowering the pixel voltage. To gain insight into the effect of parasitic coupling capacitance on the overall array performance, it is desirable to accurately and efficiently extract the capacitance during the design process. In addition, this can aid in further development of equivalent circuit models for effective SPICE-like simulations for sensitivity analysis and design optimization.
However, there are several computational difficulties in the numerical extraction of capacitance in certain electronic circuits. For example, in a-Si TFTs and imaging arrays at least three computational difficulties arise. One computational difficulty arises from the extreme device geometries, in which the ratio of thin film thickness to other physical dimensions (such as the width and length) can well be of the order of 10xe2x88x923. Another difficulty arises from the floating potential of the glass substrate, because the substrate needs to be included as part of the computational domain. A third problem arises in the treatment of multi-dielectric media, where the electric field is discontinuous across dielectric interfaces, thus requiring the computation of the electric field and therefore necessitating precise computation of the potential field. Overall, the extreme geometry of metal lines and active devices, and the presence of the glass substrate, require a large number N of panels (or mesh elements) to barely resolve the surfaces of interconnects and the interfaces between two dielectric media. This can lead to a very large system of equations.
Other computational difficulties can arise in electrical systems where the determination of capacitance is calculated based on the distribution of charge density on the surface of conductors within the system. Hence, the efficient extraction of capacitance can require the efficient evaluation of the charge density within the system. The charge density problem can be formulated in terms of a system of integral equations involving the electric potential "PHgr" and associated its gradient ∇"PHgr". However, the overall computational accuracy and performance in solving the system of integral equations lies in the evaluation of the potential "PHgr" and its gradient ∇"PHgr" at all points of interest. Therefore, the efficient evaluation of the capacitance reduces to the efficient evaluation of the potential and the electric field itself, i.e. the gradient of the potential, within the system.
In a more general context, the computation of the potential field is of interest in many research areas ranging from astrophysics, plasma, physics, molecular dynamics, to VLSI and electro-mechanical systems (xe2x80x9cMEMSxe2x80x9d). In these systems, the potential of a number of particles located throughout a three-dimensional domain and, where each particle has an associated real value (qi, i=1 . . . N) is given by the well-known 1/r dependence formula:                               Φ          ⁡                      (                          X              i                        )                          =                                            ∑              N                                                      j                =                1                            ,                              j                ≠                i                                              ⁢                                    q              j                                      "LeftDoubleBracketingBar"                                                X                  i                                -                                  X                  j                                            "RightDoubleBracketingBar"                                                          Equation        ⁢                  xe2x80x83                ⁢        1            
where:
"PHgr" is the potential
N is the number of particles
Xi, i=1 . . . N is the location of each particle
qi, i=1 . . . N is the charge of each particle
∥Xixe2x88x92Xj∥ is the distance r between each particle.
If the evaluation of Equation 1 is performed through direct pairwise particle-to-particle interactions, the computational time is of the order O(N2), which in most computers is prohibitively expensive for a large number N of particles. Prior art methods have somewhat reduced this computational time through the use of innovative operations. For example, see J. Barnes and P. Hut, xe2x80x9cA hierarchical O(N log N) force-calculation algorithmxe2x80x9d, Nature, vol 324, pp. 446-449 (xe2x80x9cBarnes and Hutxe2x80x9d). See also, L. Greengard, The Rapid Evaluation of Potential Fields in Particle Systems, MIT Press, 1988 (xe2x80x9cGreengardxe2x80x9d). See also L. Greengard and V. Rhokhlin, xe2x80x9cA new version of the fast multipole method for the Laplace equation in three dimensionsxe2x80x9d, Tech. Rep. YALEU/DCS/RR-1115, Yale University, September 1996 (xe2x80x9cGreengard/Rhokhlinxe2x80x9d).
Such prior art methods can evaluate the potential in a reduced computational time of only O(N log N) or even O(N). Computational time is reduced by the replacement of a cluster of particles with a single pseudo-particle which is representative of all particles within the cluster. Thus, subsequent steps in the operation need only determine the potential associated with the pseudo-particle. The step involved of creating of the pseudo-particle is usually referred to as a xe2x80x9ctranslationxe2x80x9d.
Underlying prior art translations is a multipole expansion (xe2x80x9cMPxe2x80x9d) operation. In multipole expansions, a tree-like hierarchy of cubes is used in the clustering of the particles and the addition theorem in spherical harmonics is the mathematical background for the translations. The order of the expansion p of the potential in terms of spherical harmonics characterizes the overall performance of the multipole-expansions. The numerical effort in the multipole-expansion method lies in obtaining the expansion coefficients efficiently through a sequence of translations, namely:
1. from source points to multipole centres, defined in the prior art as xe2x80x9cQ2Mxe2x80x9d translations;
2. from multipole centres to multipole centres, defined in the prior art as xe2x80x9cM2Mxe2x80x9d translations;
3. from multipole centres to local centres, defined in the prior art as xe2x80x9cM2Lxe2x80x9d translations;
4. from local centres to local centres, defined in the prior art as xe2x80x9cL2Lxe2x80x9d translations; and,
5. from local centres to the target point for evaluation of the potential at the target, defined in the art as xe2x80x9cL2Pxe2x80x9d translations.
Despite presenting improvements over calculations using Equation 1, certain disadvantages remain with the prior art. For example, the prior art utilizes translations with different structures: one for M2M, another for M2L, and yet another for L2L. Furthermore, Greengard involves a double sum, while Greengard/Rhokhlin involves a single sum with tight coupling between the multipole and local expansion coefficients in the spherical harmonics expansion. Another problem with the prior art is that the accuracy inherently depends on the order of the expansion p in terms of spherical harmonics and on how the M2L translations are performed. See, for example, H. Petersen, E. Smith and D. Soelvason, xe2x80x9cError estimates for the fast multi-pole method. II. The three-dimensional case,xe2x80x9d Proc. R. Soc. Lond. A, vol. 448, pp. 401-418, 1995. A third problem is that the computation time inherently depends on the order of the expansion and on the trade-off between computational time and memory in choosing the interaction list for M2L translations. The computation time is O(N log N) in Barnes and Hut, O(p4) in Greengard and O(p3) in Greengard/Rhokhlin. These speeds can be prohibitively high for certain computers and for certain large numbers of particles. A fourth problem is that the prior art can require a large amount of computer memory. The multipole and local expansion coefficients have to be stored explicitly. In Greengard, the memory requirement is O(p2), while Greengard/Rhokhlin can require O(6p2) extra memory units for storing the exponential expansion coefficients at cubes which are being affected by M2L translations. Yet another problem with the prior art is that the formulation and the evaluation of the gradient of the potential in MP methods is quite complex, as discussed in Nabors K. and White J. 1992 xe2x80x9cMultipole-accelerated capacitance extraction algorithms for 3-d structures with multipole dielectricsxe2x80x9d IEEE Trans. On Circuits and Systems, 39, 946-954.
In summary, despite prior art improvements over methods and systems utilizing direct pair-wise calculations of potentials using Equation 1, it can be seen that there is a need for another method and system for the evaluation of a field potential in three dimensions.
It is therefore an object of the present invention to provide a novel method and system for determining potential fields which obviates or mitigates at least one of the disadvantages of the prior art.
In an embodiment of the invention, there is provided a method for determining a potential using a computer having a user-input device, a processing device, and a user-output device comprising the steps of:
receiving data representing positions and charge-like measures for each of a plurality of source particles and target particles;
assigning the source particles and the target particles into at least one cluster of source particles and at least one cluster of target particles;
selecting a collection point for each of the clusters;
performing an exponential expansion operation for each of the particles to determine an inverse distance between each of the collection points and the positions of particles within their respective cluster, the exponential expansion operation being performed over a range determined from a desired level of computational precision of the distance;
defining a pseudo-particle at each of the collection points based on the inverse distances and the charge-like measures, the pseudo-particle having a position at the collection point and a charge-like measure representing the collective charge-like measures of each particle associated with the collection point; and,
determining a potential at one of the target particles based on an operation that considers at least in part the position and the charge-like measure of at least one of the pseudo-particles.
A method and system for the rapid determination of a potential in a three-dimensional domain containing a source domain of source particles and a target domain of target particles is provided. The method and system is suitable for determining a potential field, and/or its gradient, at a given target particle within the target domain, particularly in systems where there are a large number of particles. A presently preferred system includes a computer having a processing unit, monitor and keyboard and/or any other suitable user-output devices and/or user-input devices. The system is operable to execute a presently preferred method that is incorporated into the computer processing unit and receives data representative of positions and charge-like measures of each particle within the three-dimensional domain via a user-input device attached to the processing unit. The method then assigns the source particles into source particle clusters and the target particles into target particle clusters. The method then assigns a collection point to each of the clusters. Next, the method performs an exponential expansion operation on each of the particles to determine the inverse distance from the particle to the collection point of its respective cluster. The exponential expansion operation is based on an exponential integral representation of Green""s function 1/r and an approximation to the integral using Gauss quadratures. Next, a pseudo-particle representative of each particle within the cluster is defined at the collection point of each cluster. The pseudo-particle is determined from an operation that considers the inverse distances determined using the exponential expansion and the charge-like measure of each of the particles. The steps in the method are repeated until a desired level of clustering is achieved, which is generally until there is a single source pseudo-particle representative of all source particles, and a single target pseudo-particle representative all target particles. Using the gathered information, known techniques can be used to determine a potential, and/or its gradient at any of the target particles, as desired. It is generally contemplated that the method and system can be used in a variety of applications including electronics, astro-physics, plasma-physics, molecular dynamics and the like.